{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Unique Binary Search Trees II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #binary-search-tree #dynamic-programming #backtracking #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #二叉搜索树 #动态规划 #回溯 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: generateTrees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #不同的二叉搜索树 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数 <code>n</code> ，请你生成并返回所有由 <code>n</code> 个节点组成且节点值从 <code>1</code> 到 <code>n</code> 互不相同的不同 <strong>二叉搜索树</strong><em> </em>。可以按 <strong>任意顺序</strong> 返回答案。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/18/uniquebstn3.jpg\" style=\"width: 600px; height: 148px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3\n",
    "<strong>输出：</strong>[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>[[1]]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= n <= 8</code></li>\n",
    "</ul>\n",
    "</div>\n",
    "</div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [unique-binary-search-trees-ii](https://leetcode.cn/problems/unique-binary-search-trees-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [unique-binary-search-trees-ii](https://leetcode.cn/problems/unique-binary-search-trees-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3', '1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def generateTrees(self, n: int) -> List[TreeNode]:\n",
    "        def getPath(start, end):\n",
    "            trees = []\n",
    "            if start <= end:\n",
    "                for i in range(start, end+1):\n",
    "                    left = getPath(start, i-1)\n",
    "                    right = getPath(i+1, end)\n",
    "\n",
    "                    for t in left:\n",
    "                        for r in right:\n",
    "                            node = TreeNode(i)\n",
    "                            node.left = t\n",
    "                            node.right = r\n",
    "                            trees.append(node)\n",
    "                return trees\n",
    "            else:\n",
    "                return [None]\n",
    "            \n",
    "        return getPath(1, n) if n else []\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def generateTrees(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[TreeNode]\n",
    "        \"\"\"\n",
    "        if n <= 0:\n",
    "            return []\n",
    "        dp = [[[] for i in range(n)] for j in range(n)]\n",
    "        for k in range(n):\n",
    "            for i in range(n-k):\n",
    "                for j in range(i, i+k+1):\n",
    "                    #print(i, i+k, j)\n",
    "                    if k == 0:\n",
    "                        dp[i][i].append(TreeNode(i+1))\n",
    "                    elif j == i:\n",
    "                        for r in dp[j+1][i+k]:\n",
    "                            tmp = TreeNode(j+1)\n",
    "                            tmp.right = r\n",
    "                            dp[i][i+k].append(tmp)\n",
    "                            #self.print_t(tmp)\n",
    "                    elif j == i+k:\n",
    "                        for l in dp[i][j-1]:\n",
    "                            tmp = TreeNode(j+1)\n",
    "                            tmp.left = l\n",
    "                            dp[i][i+k].append(tmp)\n",
    "                            #self.print_t(tmp)\n",
    "                    else:\n",
    "                        for l in dp[i][j-1]:\n",
    "                            for r in dp[j+1][i+k]:\n",
    "                                tmp = TreeNode(j+1)\n",
    "                                tmp.left = l\n",
    "                                tmp.right = r\n",
    "                                dp[i][i+k].append(tmp)\n",
    "                                #self.print_t(tmp)\n",
    "        return dp[0][n-1]\n",
    "    \n",
    "    def print_t(self, node):\n",
    "        ret = []\n",
    "        if not node:\n",
    "            print(ret)\n",
    "            return\n",
    "        else:\n",
    "            ret.append(node.val)\n",
    "        q = [node]\n",
    "        #print(node.val)\n",
    "        while q:\n",
    "            cur = q.pop(0)\n",
    "            if cur.left:\n",
    "                #print(cur.left.val)\n",
    "                ret.append(cur.left.val)\n",
    "                q.append(cur.left)\n",
    "            elif not cur.right:\n",
    "                continue\n",
    "            else:\n",
    "                ret.append(None)\n",
    "            if cur.right:\n",
    "                #print(cur.right.val)\n",
    "                ret.append(cur.right.val)\n",
    "                q.append(cur.right)\n",
    "            else:\n",
    "                ret.append(None)\n",
    "        print(ret)\n",
    "                        \n",
    "                        \n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def generateTrees(self, n: 'int') -> 'List[TreeNode]':\n",
    "        if n == 0:return []\n",
    "        from collections import defaultdict\n",
    "        lookup = defaultdict(list)\n",
    "\n",
    "        def helper(start, end):\n",
    "            if start > end:\n",
    "                return [None]\n",
    "            if (start, end) in lookup:\n",
    "                return lookup[(start, end)]\n",
    "           \n",
    "            for val in range(start, end + 1):\n",
    "                for left in helper(start, val - 1):\n",
    "                    for right in helper(val + 1, end):\n",
    "                        root = TreeNode(val)\n",
    "                        root.left, root.right = left, right\n",
    "                        lookup[(start, end)].append(root)\n",
    "            return lookup[(start, end)]\n",
    "        return helper(1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def generateTrees(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[TreeNode]\n",
    "        \"\"\"\n",
    "        if n==0:\n",
    "            return []\n",
    "        dp = [[None for j in range(n+2)] for i in range(n+2)]\n",
    "        return self.dfs(1,n,dp)\n",
    "    \n",
    "    def dfs(self,b,e,dp):\n",
    "        if b>e:\n",
    "            return [None]\n",
    "        res = []\n",
    "        for rootVal in range(b,e+1):\n",
    "            leftTree = dp[b][rootVal-1]\n",
    "            if leftTree==None:\n",
    "                leftTree = self.dfs(b,rootVal-1,dp)\n",
    "                dp[b][rootVal-1] = leftTree\n",
    "            \n",
    "            for l in leftTree:\n",
    "                rightTree = dp[rootVal+1][e]\n",
    "                if rightTree==None:\n",
    "                    rightTree = self.dfs(rootVal+1,e,dp)\n",
    "                    dp[rootVal+1][e] = rightTree\n",
    "                for r in rightTree:\n",
    "                    root = TreeNode(rootVal)\n",
    "                    root.left = l\n",
    "                    root.right = r\n",
    "                    res.append(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def generateTrees(self, n: 'int') -> 'List[TreeNode]':\n",
    "        if n == 0:\n",
    "            return list()\n",
    "        \n",
    "        return self._generateTrees(1, n)\n",
    "        \n",
    "    def _generateTrees(self, left, right):\n",
    "        if left > right:\n",
    "            return [None]\n",
    "        \n",
    "        res = list()\n",
    "        for i in range(left, right + 1):\n",
    "            left_nodes = self._generateTrees(left, i - 1)\n",
    "            right_nodes = self._generateTrees(i + 1, right)\n",
    "            for left_node in left_nodes:\n",
    "                for right_node in right_nodes:\n",
    "                    root = TreeNode(i)\n",
    "                    root.left = left_node\n",
    "                    root.right = right_node\n",
    "                    res.append(root)\n",
    "                    \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def generateTrees(self, n: 'int') -> 'List[TreeNode]':\n",
    "        def generateHelper(s, e):\n",
    "            res = []\n",
    "            if s > e:\n",
    "                return [None]\n",
    "            if s == e:\n",
    "                return [TreeNode(s)]\n",
    "            for i in range(s, e + 1):\n",
    "                left = generateHelper(s, i - 1)\n",
    "                right = generateHelper(i + 1, e)\n",
    "                for m in left:\n",
    "                    for n in right:\n",
    "                        root = TreeNode(i)\n",
    "                        root.left = m\n",
    "                        root.right = n\n",
    "                        res.append(root)\n",
    "            return res\n",
    "        if n == 0:\n",
    "            return []\n",
    "        return generateHelper(1, n)\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def generateTrees(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[TreeNode]\n",
    "        \"\"\"\n",
    "        if n <= 0:\n",
    "            return []\n",
    "        def dfs(nums):\n",
    "            if not nums:\n",
    "                return [None]\n",
    "            res = []\n",
    "            for i in range(len(nums)):\n",
    "                for l in dfs(nums[:i]):\n",
    "                    for r in dfs(nums[i+1:]):\n",
    "                        root = TreeNode(nums[i])\n",
    "                        root.left = l\n",
    "                        root.right = r\n",
    "                        res.append(root)\n",
    "            return res\n",
    "        return dfs([i+1 for i in range(n)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def generateTrees(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[TreeNode]\n",
    "        \"\"\"\n",
    "        if not n: return []\n",
    "        def helper(m, n):\n",
    "            curr = []\n",
    "            if m > n: return [None]\n",
    "            for i in range(m, n+1):\n",
    "                # left = \n",
    "                # right = \n",
    "                for j in helper(m, i-1):\n",
    "                    for k in helper(i+1, n):\n",
    "                        tree = TreeNode(i)\n",
    "                        tree.left = j\n",
    "                        tree.right = k\n",
    "                        curr.append(tree)\n",
    "            return curr\n",
    "        return helper(1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def generateTrees(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[TreeNode]\n",
    "        \"\"\"\n",
    "        #都是采用上  左右的方式遍历树   没有的就是null  遍历到了三个数即停止\n",
    "        def generate(i,j):\n",
    "            if j-i < 0:\n",
    "                return [None]\n",
    "            elif j-i == 0:\n",
    "                return [TreeNode(i)]\n",
    "            else:\n",
    "                res = []\n",
    "                for k in range(i,j+1):\n",
    "                    left = generate(i,k-1)  #往左遍历  疯狂递归\n",
    "                    right = generate(k+1,j) #往右遍历  疯狂递归\n",
    "                    for l in left:\n",
    "                        for r in right:\n",
    "                            root = TreeNode(k)\n",
    "                            root.left = l\n",
    "                            root.right = r\n",
    "                            res.append(root)   #然后根据左右的值   二重循环往res里面添加   这题是真的强   我得背下来    脑回路无解\n",
    "                return res\n",
    "        if n == 0:\n",
    "            return []\n",
    "        else:\n",
    "            return generate(1,n)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class TreeNode1(TreeNode):\n",
    "    def __init__(self, x):\n",
    "        super(TreeNode1, self).__init__(x)\n",
    "        \n",
    "    def copy(self, Tree):\n",
    "        if Tree is None:\n",
    "            return None\n",
    "        ans = TreeNode1(Tree.val)\n",
    "        ans.left = self.copy(Tree.left)\n",
    "        ans.right = self.copy(Tree.right)\n",
    "        return ans \n",
    "    \n",
    "    # def decom(self, Tree1):\n",
    "    #     if Tree1 is None:\n",
    "    #         return None\n",
    "    #     ans = TreeNode(Tree1.val)\n",
    "    #     ans.left = self.decom(Tree1.left)\n",
    "    #     ans.right = self.decom(Tree1.right)\n",
    "    #     return ans\n",
    "    \n",
    "class Solution:\n",
    "    def generateTrees(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[TreeNode]\n",
    "        \"\"\"\n",
    "        if n == 0:\n",
    "            return []\n",
    "        ans = [TreeNode1(1)]\n",
    "        for i in range(2,n+1):\n",
    "            temp = []\n",
    "            for ele in ans:\n",
    "                x = ele.copy(ele)\n",
    "                t = TreeNode1(i)\n",
    "                t.left = x\n",
    "                temp.append(t)\n",
    "                ite = 1\n",
    "                while 1:\n",
    "                    x = ele.copy(ele)\n",
    "                    root = x\n",
    "                    for k in range(ite-1):\n",
    "                        x = x.right\n",
    "                    if x.right is None:\n",
    "                        x.right = TreeNode1(i)\n",
    "                        temp.append(root)\n",
    "                        break\n",
    "                    else:\n",
    "                        t = TreeNode1(i)\n",
    "                        t.left = x.right\n",
    "                        x.right = t\n",
    "                        temp.append(root)\n",
    "                    ite += 1\n",
    "            ans = temp\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "from copy import deepcopy\n",
    "class Solution:\n",
    "    def generateTrees(self, n: 'int') -> 'List[TreeNode]':\n",
    "        return self.addNode(TreeNode(None), 1, n)\n",
    "        \n",
    "    def addNode(self, root, m, n):\n",
    "        if m == n:\n",
    "            return [TreeNode(m)]\n",
    "        ret = []\n",
    "        for i in range(m, n + 1):\n",
    "            root.val = i\n",
    "            lefts = self.addNode(ListNode(None), m, i - 1) if i != m else [None]\n",
    "            rights = self.addNode(ListNode(None), i + 1, n) if i != n else [None]\n",
    "            for left in lefts:\n",
    "                for right in rights:\n",
    "                    root.left = left\n",
    "                    root.right = right\n",
    "                    ret.append(deepcopy(root))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "import copy\n",
    "class Solution:\n",
    "    memo = {}\n",
    "    def generateTrees(self, n):\n",
    "        def backtr(nums):\n",
    "            if len(nums) == 0:\n",
    "                return [None]\n",
    "            elif len(nums) == 1:\n",
    "                root = TreeNode(nums[0])\n",
    "                return [root]\n",
    "            else:\n",
    "                if tuple(nums) in self.memo:\n",
    "                    return self.memo[tuple(nums)]\n",
    "                res = []\n",
    "                for i in range(len(nums)):\n",
    "                    root = TreeNode(nums[i])\n",
    "                    for left in backtr(nums[:i]):\n",
    "                        root.left = left\n",
    "                        for right in backtr(nums[i+1:]):\n",
    "                            root.right = right\n",
    "                            res.append(copy.deepcopy(root))\n",
    "                self.memo[tuple(nums)] = res\n",
    "                return res\n",
    "        if n == 0:\n",
    "            return []\n",
    "        return backtr([i+1 for i in range(n)])\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[TreeNode]\n",
    "        \"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "import copy\n",
    "class Solution:\n",
    "    memo = {}\n",
    "    def generateTrees(self, n):\n",
    "        def backtr(nums):\n",
    "            if len(nums) == 0:\n",
    "                return [None]\n",
    "            elif len(nums) == 1:\n",
    "                root = TreeNode(nums[0])\n",
    "                return [root]\n",
    "            else:\n",
    "                res = []\n",
    "                for i in range(len(nums)):\n",
    "                    root = TreeNode(nums[i])\n",
    "                    for left in backtr(nums[:i]):\n",
    "                        root.left = left\n",
    "                        for right in backtr(nums[i+1:]):\n",
    "                            root.right = right\n",
    "                            res.append(copy.deepcopy(root))\n",
    "                self.memo[tuple(nums)] = res\n",
    "                return res\n",
    "        if n == 0:\n",
    "            return []\n",
    "        return backtr([i+1 for i in range(n)])\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[TreeNode]\n",
    "        \"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def generateTrees(self, n: int) -> List[TreeNode]:\n",
    "        if n == 0: return None\n",
    "        dp = [[None] * (n + 1) for _ in range(n + 1)]\n",
    "        for k in range(1, n + 1):\n",
    "            dp[k][k] = (TreeNode(k),)\n",
    "            \n",
    "        for d in range(1, n):\n",
    "            for i in range(1, n - d + 1):\n",
    "                j = i + d\n",
    "                res = []\n",
    "                for k in range(i, j + 1):\n",
    "                    lefts = dp[i][k - 1] if k > i else (None,)\n",
    "                    rights = dp[k + 1][j] if k < j else (None,)\n",
    "\n",
    "                    for left in lefts:\n",
    "                        for right in rights:\n",
    "                            node = TreeNode(k)\n",
    "                            node.left = left\n",
    "                            node.right = right\n",
    "                            res.append(node)\n",
    "                            \n",
    "                dp[i][j] = res\n",
    "                                        \n",
    "        return dp[1][n]\n",
    "                            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def generateTrees(self, n: int) -> List[TreeNode]:\n",
    "        if n < 1:\n",
    "            return []\n",
    "        trees = dict()\n",
    "        def dp_generate(start, end):\n",
    "            res = []\n",
    "            if start >= end:\n",
    "                return [None]\n",
    "            if (start, end) in trees:\n",
    "                return trees[(start,end)]\n",
    "            for idx in range(start, end):\n",
    "                leftTrees = dp_generate(start, idx)\n",
    "                rightTrees = dp_generate(idx+1, end)\n",
    "                for lt in leftTrees:\n",
    "                    for rt in rightTrees:\n",
    "                        root = TreeNode(idx)\n",
    "                        root.left = lt\n",
    "                        root.right = rt\n",
    "                        res.append(root)\n",
    "            trees[(start,end)] = res.copy()\n",
    "            return res \n",
    "        return dp_generate(1, n+1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "import functools\n",
    "class Solution:\n",
    "    def generateTrees(self, n: int) -> List[TreeNode]:\n",
    "        \n",
    "        if n == 0: return []\n",
    "        @functools.lru_cache(None)\n",
    "        def helper(start, end):\n",
    "            res = []\n",
    "            if start > end:\n",
    "                res.append(None)\n",
    "            for val in range(start, end + 1):\n",
    "                for left in helper(start, val - 1):\n",
    "                    for right in helper(val + 1, end):\n",
    "                        root = TreeNode(val)\n",
    "                        root.left = left\n",
    "                        root.right = right\n",
    "                        res.append(root)\n",
    "            return res\n",
    "\n",
    "        return helper(1, n)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def generateTrees(self, n: int) -> List[TreeNode]:\n",
    "        if n == 0: return []\n",
    "        trees = [[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            trees[0].append([TreeNode(i+1)])\n",
    "        for i in range(1, n):\n",
    "            for s in range(1, n-i+1):\n",
    "                trees[i].append([])\n",
    "                for j in range(i+1):\n",
    "                    if j == 0:\n",
    "                        for t in trees[i-1][s+j]:\n",
    "                            mid = TreeNode(s+j)\n",
    "                            mid.right = t\n",
    "                            trees[i][s-1].append(mid)\n",
    "                    elif j == i:\n",
    "                        for t in trees[i-1][s-1]:\n",
    "                            mid = TreeNode(s+j)\n",
    "                            mid.left = t\n",
    "                            trees[i][s-1].append(mid)\n",
    "                    else:\n",
    "                        for tl in trees[j-1][s-1]:\n",
    "                            for tr in trees[i-j-1][s+j]:\n",
    "                                mid = TreeNode(s+j)\n",
    "                                mid.left = tl\n",
    "                                mid.right = tr\n",
    "                                trees[i][s-1].append(mid)\n",
    "        return trees[-1][0]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def generateTrees(self, n: int) -> List[TreeNode]:\n",
    "        from functools import lru_cache\n",
    "        if n < 1:return []\n",
    "        @lru_cache(None)\n",
    "        def helper(start, end):\n",
    "            res = []\n",
    "            if start > end:\n",
    "                res.append(None)\n",
    "            for val in range(start, end + 1):\n",
    "                for left in helper(start, val-1):\n",
    "                    for right in helper(val+1, end):\n",
    "                        root = TreeNode(val)\n",
    "                        root.left = left\n",
    "                        root.right = right\n",
    "                        res.append(root)\n",
    "            return res\n",
    "        return helper(1,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def generate(self, left, right):\n",
    "        if left > right:\n",
    "            return [None]\n",
    "        if left == right:\n",
    "            return [TreeNode(left)]\n",
    "        if self.check[left][right]:\n",
    "            return self.check[left][right]\n",
    "        res = []\n",
    "        for i in range(left, right+1):\n",
    "            for left_tree in self.generate(left, i-1):\n",
    "                for right_tree in self.generate(i+1, right):\n",
    "                    head = TreeNode(i)\n",
    "                    head.left = left_tree\n",
    "                    head.right = right_tree\n",
    "                    res.append(head)\n",
    "        self.check[left][right] = res\n",
    "        return res\n",
    "\n",
    "    def generateTrees(self, n: int) -> List[TreeNode]:\n",
    "        if n == 0:\n",
    "            return []\n",
    "        self.check = {}\n",
    "        for left in range(1, n+1):\n",
    "            self.check[left] = {}\n",
    "            for right in range(1, n+1):\n",
    "                self.check[left][right] = []\n",
    "        res = self.generate(1, n)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def generateTrees(self, n: int) -> List[TreeNode]:\n",
    "        if n == 0:\n",
    "            return []\n",
    "        dct = {}\n",
    "\n",
    "        def left_right(left: int, right: int) -> List[TreeNode]:\n",
    "            if left > right:\n",
    "                return [None]\n",
    "            if (left, right) in dct:\n",
    "                return dct[(left, right)]\n",
    "            ret = []\n",
    "            for i in range(left, right+1):\n",
    "                left_lst = left_right(left, i-1)\n",
    "                right_lst = left_right(i+1, right)\n",
    "                for L in left_lst:\n",
    "                    for R in right_lst:\n",
    "                        app_Tree = TreeNode(i)\n",
    "                        app_Tree.left = L\n",
    "                        app_Tree.right = R\n",
    "                        ret.append(app_Tree)\n",
    "            dct[(left, right)] = ret\n",
    "            return ret\n",
    "\n",
    "        return left_right(1, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def generateTrees(self, n: int) -> List[TreeNode]:\n",
    "        if n <  1:\n",
    "            return []\n",
    "        mem_dic = {}\n",
    "        def all_per(start, end):\n",
    "            if start > end:\n",
    "                return [None]\n",
    "            if (start, end) in mem_dic:\n",
    "                return mem_dic[(start,end)]\n",
    "            res = []\n",
    "            for i in range(start, end+1):\n",
    "                left_lst = all_per(start, i-1)\n",
    "                right_lst = all_per(i+1, end)\n",
    "                for L in left_lst:\n",
    "                    for R in right_lst:\n",
    "                        app_Tree = TreeNode(i)\n",
    "                        app_Tree.left = L\n",
    "                        app_Tree.right = R\n",
    "                        res.append(app_Tree)\n",
    "            mem_dic[(start,end)] = res\n",
    "            return res\n",
    "        return all_per(1,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def generateTrees(self, n: int) -> List[TreeNode]:\n",
    "        if n==0:\n",
    "            return []\n",
    "        \n",
    "\n",
    "        def dfs(left,right):\n",
    "            res=[]\n",
    "            if left>right:\n",
    "                return [None,]\n",
    "            for i in range(left,right+1):\n",
    "                left_trees = dfs(left,i-1)\n",
    "                right_trees = dfs(i+1,right)\n",
    "                for m in left_trees:\n",
    "                    for n in right_trees:\n",
    "                        cur = TreeNode(i)\n",
    "                        cur.left = m\n",
    "                        cur.right = n\n",
    "                        res.append(cur)\n",
    "            return res\n",
    "        return dfs(1,n)\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def generateTrees(self, n: int) -> List[TreeNode]:\n",
    "        if n==0:\n",
    "            return []\n",
    "        def regenerateTrees(left,right):\n",
    "            if left>right:\n",
    "                return [None]\n",
    "            allTrees = []\n",
    "            for i in range(left,right+1):\n",
    "                leftTrees = regenerateTrees(left,i-1)\n",
    "                rightTrees = regenerateTrees(i+1,right)\n",
    "                for l in leftTrees:\n",
    "                    for r in rightTrees:\n",
    "                        p = TreeNode(i)\n",
    "                        p.left = l\n",
    "                        p.right = r\n",
    "                        allTrees.append(p)\n",
    "            return allTrees\n",
    "        return regenerateTrees(1,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def generateTrees(self, n: int) -> List[TreeNode]:\n",
    "        if n == 0:\n",
    "            return []\n",
    "        dct = {}\n",
    "\n",
    "        def left_right(left: int, right: int) -> List[TreeNode]:\n",
    "            if left > right:\n",
    "                return [None]\n",
    "            if (left, right) in dct:\n",
    "                return dct[(left, right)]\n",
    "            ret = []\n",
    "            for i in range(left, right+1):\n",
    "                left_lst = left_right(left, i-1)\n",
    "                right_lst = left_right(i+1, right)\n",
    "                for L in left_lst:\n",
    "                    for R in right_lst:\n",
    "                        app_Tree = TreeNode(i)\n",
    "                        app_Tree.left = L\n",
    "                        app_Tree.right = R\n",
    "                        ret.append(app_Tree)\n",
    "            dct[(left, right)] = ret\n",
    "            return ret\n",
    "\n",
    "        return left_right(1, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    import functools\n",
    "    def generateTrees(self, n: int) -> List[TreeNode]:\n",
    "        if n == 0: return []\n",
    "        @functools.lru_cache(None)\n",
    "        def helper(start, end):\n",
    "            res = []\n",
    "            if start > end:\n",
    "                res.append(None)\n",
    "            for val in range(start, end + 1):\n",
    "                for left in helper(start, val - 1):\n",
    "                    for right in helper(val + 1, end):\n",
    "                        root = TreeNode(val)\n",
    "                        root.left = left\n",
    "                        root.right = right\n",
    "                        res.append(root)\n",
    "            return res\n",
    "\n",
    "        return helper(1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:\n",
    "        @cache\n",
    "        def rec(start,end):\n",
    "            if start > end:\n",
    "                return [None]\n",
    "            res = []\n",
    "            for i in range(start,end+1):\n",
    "                left = rec(start,i-1)\n",
    "                right = rec(i+1,end)\n",
    "                for l in left:\n",
    "                    for r in right:\n",
    "                        newroot = TreeNode(i)\n",
    "                        newroot.left = l\n",
    "                        newroot.right = r\n",
    "                        res.append(newroot)\n",
    "            return res\n",
    "        \n",
    "        return rec(1,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:\n",
    "        res = []\n",
    "        cache = {}\n",
    "\n",
    "        def dfs(l, r):\n",
    "            if r - l < 0:\n",
    "                return [None]\n",
    "            key = str(l) + '_' + str(r)\n",
    "            if key in cache:\n",
    "                return cache[key]\n",
    "\n",
    "            res = []\n",
    "            for i in range(l, r + 1):\n",
    "                lCan = dfs(l, i - 1)\n",
    "                rCan = dfs(i + 1, r)\n",
    "                for ln in lCan:\n",
    "                    for rn in rCan:\n",
    "                        root = TreeNode(i, ln, rn)\n",
    "                        res.append(root)\n",
    "            cache[key] = res\n",
    "            return res\n",
    "        \n",
    "        \n",
    "        return dfs(1, n)\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import functools\n",
    "class Solution:\n",
    "    def generateTrees(self, n: int) -> List[TreeNode]:\n",
    "        if n == 0: return []\n",
    "        @functools.lru_cache(None)\n",
    "        def helper(start, end):\n",
    "            res = []\n",
    "            if start > end:\n",
    "                res.append(None)\n",
    "            for val in range(start, end + 1):\n",
    "                for left in helper(start, val - 1):\n",
    "                    for right in helper(val + 1, end):\n",
    "                        root = TreeNode(val)\n",
    "                        root.left = left\n",
    "                        root.right = right\n",
    "                        res.append(root)\n",
    "            return res\n",
    "\n",
    "        return helper(1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    treeMap = {}\n",
    "    def constructAndCopy(self,val:int,left:Optional[TreeNode],right:Optional[TreeNode])->Optional[TreeNode]:\n",
    "        root = TreeNode(val)\n",
    "        root.left = None if not left else TreeNode(left.val,left.left,left.right)\n",
    "        root.right = None if not right else TreeNode(right.val,right.left,right.right)\n",
    "        return root\n",
    "    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:\n",
    "        # level = 0\n",
    "        # possible_levels = []\n",
    "        # while 2 ** level <= n:\n",
    "        #     possible_levels.append(level)\n",
    "        #     level += 1\n",
    "        subN = list(range(1,n+1))\n",
    "        def build(x:int,y:int)-> List[Optional[TreeNode]]:\n",
    "            # leftsubTree = []\n",
    "            # rightsubTree = []\n",
    "            if x >= y:\n",
    "                return []\n",
    "            if y - 1 == x:\n",
    "                return [TreeNode(subN[x])]\n",
    "            if (x,y) in self.treeMap:\n",
    "                return self.treeMap[(x,y)]\n",
    "            candidates = []\n",
    "            for i in range(x,y):\n",
    "                curr = subN[i]\n",
    "                # [ 2 ], [1][3 4], \n",
    "                # [ ] root=3 [ 1 2]\n",
    "                lefts = build(x,i) \n",
    "                rights = build(i+1,y)\n",
    "                if lefts and rights:\n",
    "                    for l in lefts:\n",
    "                        for r in rights:\n",
    "                    # for l,r in zip(lefts,rights) :\n",
    "                            root = self.constructAndCopy(curr,l,r)\n",
    "                            candidates.append(root)\n",
    "                elif lefts:\n",
    "                    for l in lefts:\n",
    "                        root = self.constructAndCopy(curr,l,None)\n",
    "                        candidates.append(root)\n",
    "                elif rights:\n",
    "                    for r in rights:\n",
    "                        root = self.constructAndCopy(curr,None,r)\n",
    "                        candidates.append(root)\n",
    "                else:\n",
    "                    root = self.constructAndCopy(curr,None,None)\n",
    "                    candidates.append(root)\n",
    "            self.treeMap[(x,y)] = candidates\n",
    "            return candidates\n",
    "        res = build(0,n)\n",
    "        return res\n",
    "        # def build(subN:List[int])-> List[Optional[TreeNode]]:\n",
    "        #     # leftsubTree = []\n",
    "        #     # rightsubTree = []\n",
    "        #     if not subN:\n",
    "        #         return []\n",
    "        #     if len(subN) == 1:\n",
    "        #         return [TreeNode(subN[0])]\n",
    "        #     candidates = []\n",
    "        #     for i in range(0,len(subN)):\n",
    "        #         curr = subN[i]\n",
    "        #         # [ 3 ] [ 1 2]\n",
    "        #         # [ ] root=3 [ 1 2]\n",
    "        #         lefts = build(subN[0:i]) \n",
    "        #         rights = build(subN[i+1:len(subN)])\n",
    "        #         if lefts:\n",
    "        #             for l in lefts:\n",
    "        #                 if rights:\n",
    "        #                     for r in rights:\n",
    "        #                         root = self.constructAndCopy(curr,l,r)\n",
    "        #                         candidates.append(root)\n",
    "        #                 else:\n",
    "        #                     root = self.constructAndCopy(curr,l,None)\n",
    "        #                     candidates.append(root)\n",
    "        #         else:\n",
    "        #             if rights:\n",
    "        #                 for r in rights:\n",
    "        #                     root = self.constructAndCopy(curr,None,r)\n",
    "        #                     candidates.append(root)\n",
    "                        \n",
    "        #     return candidates\n",
    "        # res = build(list(range(1,n+1)))\n",
    "        # return res\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    treeMap = {}\n",
    "    def constructAndCopy(self,val:int,left:Optional[TreeNode],right:Optional[TreeNode])->Optional[TreeNode]:\n",
    "        root = TreeNode(val)\n",
    "        root.left = None if not left else TreeNode(left.val,left.left,left.right)\n",
    "        root.right = None if not right else TreeNode(right.val,right.left,right.right)\n",
    "        return root\n",
    "    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:\n",
    "        # level = 0\n",
    "        # possible_levels = []\n",
    "        # while 2 ** level <= n:\n",
    "        #     possible_levels.append(level)\n",
    "        #     level += 1\n",
    "        subN = list(range(1,n+1))\n",
    "        def build(x:int,y:int)-> List[Optional[TreeNode]]:\n",
    "            # leftsubTree = []\n",
    "            # rightsubTree = []\n",
    "            if x >= y:\n",
    "                return []\n",
    "            if y - 1 == x:\n",
    "                return [TreeNode(subN[x])]\n",
    "            if (x,y) in self.treeMap:\n",
    "                return self.treeMap[(x,y)]\n",
    "            candidates = []\n",
    "            for i in range(x,y):\n",
    "                curr = subN[i]\n",
    "                # [ 2 ], [1][3 4], \n",
    "                # [ ] root=3 [ 1 2]\n",
    "                lefts = build(x,i) \n",
    "                rights = build(i+1,y)\n",
    "                if lefts and rights:\n",
    "                    # 不清楚什么原因 但是这里用zip不会每次都走全\n",
    "                    # for (l,r) in list(zip(lefts,rights)):\n",
    "                    for l in lefts:\n",
    "                        for r in rights:\n",
    "                            root = self.constructAndCopy(curr,l,r)\n",
    "                            candidates.append(root)\n",
    "                            \n",
    "\n",
    "                elif lefts:\n",
    "                    for l in lefts:\n",
    "                        root = self.constructAndCopy(curr,l,None)\n",
    "                        candidates.append(root)\n",
    "                elif rights:\n",
    "                    for r in rights:\n",
    "                        root = self.constructAndCopy(curr,None,r)\n",
    "                        candidates.append(root)\n",
    "                else:\n",
    "                    root = self.constructAndCopy(curr,None,None)\n",
    "                    candidates.append(root)\n",
    "            self.treeMap[(x,y)] = candidates\n",
    "            return candidates\n",
    "        res = build(0,n)\n",
    "        return res\n",
    "        # def build(subN:List[int])-> List[Optional[TreeNode]]:\n",
    "        #     # leftsubTree = []\n",
    "        #     # rightsubTree = []\n",
    "        #     if not subN:\n",
    "        #         return []\n",
    "        #     if len(subN) == 1:\n",
    "        #         return [TreeNode(subN[0])]\n",
    "        #     candidates = []\n",
    "        #     for i in range(0,len(subN)):\n",
    "        #         curr = subN[i]\n",
    "        #         # [ 3 ] [ 1 2]\n",
    "        #         # [ ] root=3 [ 1 2]\n",
    "        #         lefts = build(subN[0:i]) \n",
    "        #         rights = build(subN[i+1:len(subN)])\n",
    "        #         if lefts:\n",
    "        #             for l in lefts:\n",
    "        #                 if rights:\n",
    "        #                     for r in rights:\n",
    "        #                         root = self.constructAndCopy(curr,l,r)\n",
    "        #                         candidates.append(root)\n",
    "        #                 else:\n",
    "        #                     root = self.constructAndCopy(curr,l,None)\n",
    "        #                     candidates.append(root)\n",
    "        #         else:\n",
    "        #             if rights:\n",
    "        #                 for r in rights:\n",
    "        #                     root = self.constructAndCopy(curr,None,r)\n",
    "        #                     candidates.append(root)\n",
    "                        \n",
    "        #     return candidates\n",
    "        # res = build(list(range(1,n+1)))\n",
    "        # return res\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    \n",
    "    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:\n",
    "        @cache\n",
    "        def TreeInit(left,right):\n",
    "            if left == right:\n",
    "                return [TreeNode(left)]\n",
    "\n",
    "            res = []\n",
    "            for i in range(left,right+1):\n",
    "                leftnodes = TreeInit(left,i-1)\n",
    "                rightnodess = TreeInit(i+1,right)\n",
    "                if leftnodes and rightnodess:\n",
    "                    for leftnode in leftnodes:\n",
    "                        for rightnode in rightnodess:\n",
    "                            res.append(TreeNode(i,leftnode,rightnode))\n",
    "                elif leftnodes:\n",
    "                    for leftnode in leftnodes:\n",
    "                        res.append(TreeNode(i,leftnode,None))\n",
    "                else:\n",
    "                    for rightnode in rightnodess:\n",
    "                        res.append(TreeNode(i,None,rightnode))\n",
    "\n",
    "            return res\n",
    "        return TreeInit(1,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:\n",
    "        @lru_cache\n",
    "        def dfs(l, r):\n",
    "            if l > r:\n",
    "                return [None]\n",
    "            ans = []\n",
    "            for i in range(l, r+1):\n",
    "                for x in dfs(l, i-1):\n",
    "                    for y in dfs(i+1, r):\n",
    "                        root = TreeNode(i)\n",
    "                        root.left, root.right = x, y\n",
    "                        ans.append(root)\n",
    "            return ans\n",
    "        return dfs(1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:\n",
    "        @lru_cache\n",
    "        def dfs(l, r):\n",
    "            if l > r:\n",
    "                return [None]\n",
    "            ans = []\n",
    "            for i in range(l, r+1):\n",
    "                for x in dfs(l, i-1):\n",
    "                    for y in dfs(i+1, r):\n",
    "                        root = TreeNode(i)\n",
    "                        root.left, root.right = x, y\n",
    "                        ans.append(root)\n",
    "            return ans\n",
    "        return dfs(1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:\n",
    "        if n == 0: return []\n",
    "        return self.dfs(1, n)\n",
    "    def dfs(self, l, r):\n",
    "        if l > r: return [None]\n",
    "        if l == r: return [TreeNode(l)]\n",
    "        res = []\n",
    "        for i in range(l, r + 1):\n",
    "            lTrees = self.dfs(l, i - 1)\n",
    "            rTrees = self.dfs(i + 1, r)\n",
    "            for lTree in lTrees:\n",
    "                for rTree in rTrees:\n",
    "                    root = TreeNode(i)\n",
    "                    root.left = lTree\n",
    "                    root.right = rTree\n",
    "                    res.append(root)\n",
    "        return res\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:\n",
    "        result=[]\n",
    "        root=TreeNode\n",
    "        def tree(nums):\n",
    "            if not nums:\n",
    "                return [None]\n",
    "            r=[]\n",
    "            for i in range(len(nums)):\n",
    "                \n",
    "                lefts=tree(nums[:i])\n",
    "                rights=tree(nums[i+1:])\n",
    "                for left in lefts:\n",
    "                    for right in rights:\n",
    "                        t=TreeNode(nums[i])\n",
    "                        t.left=left\n",
    "                        t.right=right\n",
    "                        r.append(t)\n",
    "            return r\n",
    "        return tree([i+1 for i in range(n)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:\n",
    "        def gen(start, end):\n",
    "            if start>end:\n",
    "                return [None,]\n",
    "            alltree = []\n",
    "\n",
    "            for i in range(start, end+1):\n",
    "                lefttree = gen(start, i-1)\n",
    "                righttree = gen(i+1, end)\n",
    "                for l in lefttree:\n",
    "                    for r in righttree:\n",
    "                        currtree = TreeNode(i)\n",
    "                        currtree.left = l\n",
    "                        currtree.right = r\n",
    "                        alltree.append(currtree)\n",
    "            return alltree\n",
    "        \n",
    "        return gen(1, n) if n else []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:\n",
    "        def dfs(l, r):\n",
    "            if l > r:\n",
    "                return [None]\n",
    "            ans = []\n",
    "            for i in range(l, r+1):\n",
    "                for x in dfs(l, i-1):\n",
    "                    for y in dfs(i+1, r):\n",
    "                        root = TreeNode(i)\n",
    "                        root.left, root.right = x, y\n",
    "                        ans.append(root)\n",
    "            return ans\n",
    "        return dfs(1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from copy import deepcopy\n",
    "class Solution:\n",
    "    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:\n",
    "        def dfs(l, r):\n",
    "            if l > r:\n",
    "                return [None]\n",
    "            ans = []\n",
    "            for i in range(l, r + 1):\n",
    "                for x in dfs(l, i - 1):\n",
    "                    for y in dfs(i + 1, r):\n",
    "                        root = TreeNode(i)\n",
    "                        root.left, root.right = x, y\n",
    "                        ans.append(root)\n",
    "            return ans\n",
    "        return dfs(1, n)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:\n",
    "        if n == 1:\n",
    "            return [TreeNode(val=1)]\n",
    "        def cloneNode(root):\n",
    "            if not root:\n",
    "                return root\n",
    "            node = TreeNode(root.val)\n",
    "            node.left = cloneNode(root.left)\n",
    "            node.right = cloneNode(root.right)\n",
    "            return node\n",
    "        def dfs(l,r):\n",
    "            res = []\n",
    "            if l > r :\n",
    "                return [None]\n",
    "            if l == r:\n",
    "                return [TreeNode(val=l)]\n",
    "            for i in range(l,r+1):\n",
    "                root = TreeNode(i)\n",
    "                left_parts = dfs(l,i-1)\n",
    "                right_parts = dfs(i+1,r)\n",
    "                for l_node in left_parts:\n",
    "                    for r_node in right_parts:\n",
    "                        root.left = l_node\n",
    "                        root.right = r_node\n",
    "                        res.append(cloneNode(root)) # 注意深度拷贝，避免引用问题\n",
    "\n",
    "            return res\n",
    "        return dfs(1,n)\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
